Problem statement: zenit12ckg

Farmár Ján má N výbehov, v ktorých chová kozičky. Výbehy má usporiadané v jednom dlhom rade. V každom výbehu môže mať jednu alebo žiadnu kozičku.

Farmár Michal bol u Jána na návšteve. Prešiel sa okolo výbehov od jedného konca k druhému. Ku každému sa postavil a pozrel, či je v ňom kozička a či sú kozičky v dvoch susedných výbehoch. Počet kozičiek, ktoré videl, si zapísal. Takto dostal postupnosť N čísel, ktoré ukázal Jánovi. Keďže v každom momente videl najviac do troch ohrád, žiadne z týchto čísel nepresahuje tri. Keď stál pri krajnej ohrade, videl samozrejme najviac dve kozičky.

Keďže Ján má výbehov veľmi veľa, nepamätá si presne, v ktorých sa momentálne nachádzajú kozičky a ktoré sú prázdne. Pozrel sa na Michalove čísla a začal skúšať toto rozmiestnenie zrekonštruovať. Potom si ale uvedomil, že to vlastne vôbec nemusí byť jednoznačné a keďže momentálne nemá čas, ocenil by aspoň program, ktorý mu vypočíta počet možností.

Na prvom riadku vstupu je celé číslo N, pre ktoré platí 2 ≤ N ≤ 1,000. Na druhom riadku vstupu je Michalova postupnosť N medzerou oddelených čísel. Každé z nich je rovné 0,1,2 alebo 3. Prvé ani posledné číslo nebude 3.

Na jediný riadok výstupu vypíšte počet rozmiestnení kozičiek do výbehov tak, aby zodpovedali daným Michalovým pozorovaniam. Dve rozmiestnenia sú rôzne, ak existuje ohrada, v ktorej je v jednom rozmiestnení kozička a v druhom nie je. V prípade, že toto číslo presahuje miliardu vypíšte namiesto odpovede slovo VELA.

2
1 1

    
  

2

    
  

4
1 2 1 0

    
  

0

    
  

4
2 3 3 2

    
  

1